package Array;

/**
 * 122. 买卖股票的最佳时机 II
 *  给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
 * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
  解题思路：
    通过这道题分析，可以得出，当天的利润 可以分为 前一天获取的最大利润 + 当天是否能获取利润， 这种由前一天推导出后一天的情况，我们就可以使用动态规划。
  解题步骤：
    1： 创建一个dp数组，dp的长度是prices的长度， 第一天的利润肯定是0，所以 dp[0] = 0;
    2: 从第二天起开始计算， 每一天获取的利润都是由前一天的实时价格差决定，分为两种情况：
      （1） 当天i的价格小于前一天，当天肯定没有利润， 所以 dp[i] = dp[i-1] +0 , 证明当天的最大利润还是前一天的最大利润；
      （2） 当天i的价格大于前一天，证明当天能获取到利润，所以 dp[i] = dp[i-1] + (prices[i] - prices[i-1])), 证明前一天的利润加上当天的利润，则是最大利润
    3： 状态转移方程 : 翻译步骤2， dp[i] = dp[i-1] + if(prices[i] > prices[i-1]) {prices[i] - prices[i-1]} else 0;
    4: 数组遍历完毕，返回dp[prices.length-1]即可。
  翻译代码：
 */
public class MaxProfit {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1){
            return 0; // 无利润
        }
        //定义状态转移方程
        int[] dp = new int[prices.length];
        dp[0] = 0;
        for (int i = 1; i <prices.length; i++) {
            if(prices[i] > prices[i-1]){
                dp[i] = dp[i-1] + (prices[i] - prices[i-1]);  // 前一天的最大利润加上当天的利润
            }else{
                dp[i] = dp[i-1] + 0; // +0 没利润
            }
        }
        return dp[prices.length-1];
    }
}
